package BinaryTree;

//完全二叉树的节点个数: https://leetcode.cn/problems/count-complete-tree-nodes/description/
//时间复杂度: O((log(n))^2)
public class CountNodes {
	//方法一:
	
	public int dfs1(TreeNode root){
        if(root==null) return 0;
        int h1=0,h2=1;
        TreeNode leftRoot=root,rightRoot=root.right;
        while(leftRoot!=null){    //计算当前节点的最大高度
            h1++;
            leftRoot=leftRoot.left;
        }
        while(rightRoot!=null){   //计算当前节点右孩子的最大高度+1(初值为1，因此未写+1)
            h2++;
            rightRoot=rightRoot.left;
        }
        if(h2==h1) return (int)(Math.pow(2,h1-1))+dfs1(root.right);
        else return (int)(Math.pow(2,h2-1))+dfs1(root.left,h-1);
    }
    public int countNodes1(TreeNode root) {
        return dfs1(root);
    }
    
    
    //方法二:
    
	//给定节点，计算该节点到最底层的高度，设初始高度为1
	public static int mostLeft(TreeNode cur,int level) {
		while(cur!=null) {
			level++;
			cur=cur.left;
		}
		return level-1;
	}
	
	//cur: 当前节点
	//h: 整颗完全二叉树的高度，不是当前节点到底部的高度
	//level: 当前节点所在的高度
	//dfs: 计算当前节点cur的节点个数
	public static int dfs2(TreeNode cur,int level,int h) {
		if(level==h) return 1;   //如果cur在最后一层，即叶子节点，显然节点数为1
		if(mostLeft(cur.right, level+1)==h) { 
			return (1<<(h-level))+dfs2(cur.right,level+1,h); //再以右孩子为根，因此level+1
		}
		else {
			return (1<<(h-level-1))+dfs2(cur.left,level+1,h);//再以右孩子为根，因此level+1
		}
	}
	public int countNodes2(TreeNode root) {
        if(root==null) {
        	return 0;
        }
        return dfs2(root,1,mostLeft(root, 1));
    }
}
